`
https://leetcode.cn/problems/generate-parentheses/
`

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  const track = []
  const res = []

  const backtrack = (left, right) => {
      // 若左括号剩下的多，说明不合法
      if (right < left) return
      // 数量小于 0 肯定是不合法的
      if (left < 0 || right < 0) return
      // 当所有括号都恰好用完时，得到一个合法的括号组合
      if (left === 0 && right === 0) {
          res.push(track.join(''))
          return
      }

      // 做选择，尝试放一个左括号
      track.push('(')
      backtrack(left - 1, right)
      // 撤销选择
      track.pop()

      // 做选择，尝试放一个右括号
      track.push(')')
      backtrack(left, right - 1)
      // 撤销选择
      track.pop()
  }

  backtrack(n, n)
  return res
};